package algorithm.dynamic_planning.leetcode;

import java.util.Arrays;

/**
 * @author yuisama
 * @date 2022/12/05 16:01
 * 俄罗斯套娃信封
 * 二维数组的LIS问题
 *
 **/
public class Num354_MaxEnvelopes {
    // 先按照宽度w排序，然后相同的w对高度h做降序，得到的h数组上求LIS即可
    public int maxEnvelopes(int[][] envelopes) {
        // o[0]是w
        // o[1]是h
        // 默认按宽度w排序，w相同按照高度降序
        Arrays.sort(envelopes, (o1,o2) -> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]);
        int[] newH = new int[envelopes.length];
        for (int i = 0; i < newH.length; i++) {
            newH[i] = envelopes[i][1];
        }
        return LIS(newH);
    }

    public int LIS(int[] nums) {
        int[] top = new int[nums.length];
        // 牌堆数初始化为 0
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            // 要处理的扑克牌
            int poker = nums[i];

            /***** 搜索左侧边界的二分查找 *****/
            int left = 0, right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            /*********************************/

            // 没找到合适的牌堆，新建一堆
            if (left == piles) piles++;
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        // 牌堆数就是 LIS 长度
        return piles;
    }
}